'''
递归函数
    递归算法简洁明了
    递归算法需要占用大量的内存空间，所以受递归深度的限制
    尾递归不受递归深度的限制
'''

# n! = n * (n-1)*(n-2)*...*2*1
def fact(n):
    s = 1
    for i in range(1,n+1):
        s *= i  # s = s * i
    return s

print(fact(5))


'''
降维
n! = n * (n-1)*(n-2)*...*2*1
n! = n *(n-1)!
(n-1)! = (n-1)*(n-2)!
..
2! = 2*(2-1)!
1！= 1
'''

# 求n!
# 递归函数
def f(n):
    if n == 1:  # 2.边界条件-终止递归调用的条件
        return 1
    return n * f(n-1) # 1.自己调用自己-递归调用

print(f(5))

'''
f(5)
5 * f(4)
5 * (4 * f(3))
5 * (4 * (3 * f(2)))
5 * (4 * (3 * (2* f(1))))
5 * (4 * (3 * (2* 1))))
5 * (4 * (3 * 2)))
5 * (4 * 6)
5 * 24
120
'''

print(fact(1000))
# RecursionError: maximum recursion depth exceeded in comparison
print(f(1000))